package com.mj.listen2._04_递归;

public class Fib {
    public int fib(int n) {
        if (n <= 2) return 1;
        return fib(n - 1) + fib(n - 2);
    }

    public int fib2(int n) {
        if (n <= 2) return 1;
        // 使用数组保存上一次递归返回结果，就是第 n 个数的斐波那契数列值
        // 浪费 arr[0] 这个位置
        int[] arr = new int[n + 1];
        arr[1] = arr[2] = 1;
        return fib2(n, arr);
    }

    public int fib2(int n, int[] arr) {
        if (arr[n] == 0) {
            arr[n] = fib2(n - 1, arr) + fib2(n - 2, arr);
        }
        return arr[n];
    }
}

